home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / war_seq.icl < prev   
Text File  |  1992-08-07  |  2KB  |  74 lines
  1. MODULE war_seq;
  2.  
  3. <<
  4. Sequential version of Warshall's shortest path algorithm
  5.  
  6. Calculates the lenghts of the shortest paths between all nodes of
  7. a directed graph represented by its adjacency matrix using Warshall's
  8. algorithm. The result of the program will be a matrix containing the
  9. length of the shortest path between node i and node j on index (i,j).
  10. >>
  11.  
  12. FROM deltaI IMPORT --, ++, +, >;
  13.  
  14.  
  15. TYPE
  16.  
  17. ::  Row -> [INT];   == A row is represented as a list of integers.
  18. ::  Mat -> [Row];   == A matrix is represented as a list of rows.
  19.  
  20.  
  21. MACRO
  22.  
  23.     Size -> 6;      == The size of the initial matrix.
  24.     
  25.  
  26. RULE
  27.  
  28. ==  The initial matrix.
  29.  
  30. ::  InitMat -> Mat;                             ==   Shortest path matrix:
  31.     InitMat ->  [[  0,100,100, 13,100,100  ],   == [  0, 16,100, 13, 20, 20 ]
  32.                 [ 100,  0,100,100,  4,  9  ],   == [ 19,  0,100,  5,  4,  9 ]
  33.                 [  11,100,  0,100,100,100  ],   == [ 11, 27,  0, 24, 31, 31 ]
  34.                 [ 100,  3,100,  0,100,  7  ],   == [ 18,  3,100,  0,  7,  7 ]
  35.                 [  15,  5,100,  1,  0,100  ],   == [ 15,  4,100,  1,  0,  8 ]
  36.                 [  11,100,100, 14,100,  0 ]];   == [ 11, 17,100, 14, 21,  0 ]
  37.  
  38.  
  39. ==  Miscellaneous functions.
  40.  
  41. ::  Min INT INT -> INT;
  42.     Min i j -> j, IF > i j
  43.             -> i;
  44.  
  45. ::  Select [x] INT -> x; 
  46.     Select [f|r] 1 -> f;
  47.     Select [f|r] k -> Select r (-- k);
  48.  
  49.  
  50. ==  Warshall's shortest path algorithm.
  51.  
  52. ::  Warshall Mat -> Mat;
  53.     Warshall mat -> Iterate 1 mat;
  54.  
  55. ::  Iterate INT Mat -> Mat;
  56.     Iterate i mat   -> mat, IF > i Size
  57.                     -> Iterate (++ i) (WarRows i mat (Select mat i));
  58.  
  59. ::  WarRows INT Mat Row -> Mat;
  60.     WarRows i [] rowi -> [];
  61.     WarRows i [rowj|rs] rowi
  62.     -> [ UpdateRow (Select rowj i) rowj rowi | WarRows i rs rowi ];
  63.     
  64. ::  UpdateRow INT Row Row -> Row;
  65.     UpdateRow ji [] [] -> [];
  66.     UpdateRow ji [jk|rjs] [ik|ris]
  67.     -> [ Min jk (+ ji ik) | UpdateRow ji rjs ris ];
  68.  
  69.  
  70. ==  The Start rule: apply Warshall's algorithm on the initial matrix.
  71.  
  72. ::  Start -> Mat;
  73.     Start -> Warshall InitMat;
  74.